package com.husk.leetcode.search;

/**
 * <p>
 * 折半查找法
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/29
 */
public class BinarySearch {


    /**
     * 704. 二分查找
     * <p>
     * https://leetcode-cn.com/problems/binary-search/
     *
     * @param nums   升序有序数组
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // 没有匹配的元素
        return -1;
    }

    /**
     * 35. 搜索插入位置
     * <p>
     * https://leetcode-cn.com/problems/search-insert-position/
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0 || nums[0] > target) {
            return 0;
        }
        if (nums[len - 1] < target) {
            return len;
        }

        int low = 0;
        int high = len - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    /**
     * 162. 寻找峰值
     * <p>
     * https://leetcode-cn.com/problems/find-peak-element/solution/
     *
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        // TODO
        
        return 0;
    }

    /**
     * 74. 搜索二维矩阵
     * <p>
     * https://leetcode-cn.com/problems/search-a-2d-matrix/
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // TODO

        return false;
    }

}
